package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.DynamicProblem;
import cn.pugle.oj.catalog.StackProblem;

import java.util.Stack;

/**
 * 直方图最大面积-Largest Rectangle in Histogram
 * http://www.acmerblog.com/largest-rectangle-in-histogram-6117.html
 * <p> Created by tzp on 2017/8/24.
 */
public class LC84 implements StackProblem, DynamicProblem {
    public static int largestRectangleArea(int[] height) {
        int area = 0;
        Stack<Integer> stack = new Stack<Integer>();
        for (int i = 0; i < height.length; i++) {
            if (stack.empty() || height[stack.peek()] < height[i]) {
                stack.push(i);
            } else {
                int start = stack.pop();
                int width = stack.empty() ? i : i - stack.peek() - 1;
                area = Math.max(area, height[start] * width);
                i--;
            }
        }
        while (!stack.empty()) {
            int start = stack.pop();
            int width = stack.empty() ? height.length : height.length - stack.peek() - 1;
            area = Math.max(area, height[start] * width);
        }
        return area;
    }

    public static void main(String[] args) {
        System.out.println(largestRectangleArea(new int[]{2, 1, 3, 5, 6, 3}));
    }
}
